package demo7;

import java.util.*;

public class Solution {

    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(!stack.isEmpty()||cur!=null){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right!=null&&top.right!=prev){
                cur = top.right;
                prev = cur;
            }else {
                res.add(top.val);
                stack.pop();
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(1);
        //TreeNode node4 = new TreeNode(5);
        node1.right = node2;
        node2.right = node3;
//        TreeNode node5 = new TreeNode(2);
//        TreeNode node6 = new TreeNode(1);
//        TreeNode node7 = new TreeNode(3);
//        TreeNode node8 = new TreeNode(4);
//        TreeNode node9 = new TreeNode(7);
//        node5.left = node6;
//        node5.right = node7;
//        node6.right = node8;
//        node7.right = node9;
        Solution solution = new Solution();
//        int[] a1 = {9,3,15,20,7};
//        int[] a2 = {9,15,7,20,3};
        solution.postorderTraversal(node1);

    }


}